# 和为K的子数组 : https://leetcode-cn.com/problems/subarray-sum-equals-k/


# 类似于暴力解法了，还浪费了空间计算出前缀和数组， 暴力破解是在过程中计算区间和 每次区间 j += 1, 区间和也是 + nums[j]
class Solution:
    def subarraySum(self, nums: list, k: int) -> int:
        """
            计算前缀和，线性查找
        """
        # 计算前缀和
        n = len(nums)
        prefixList = [0] * (n + 1)
        for i in range(len(nums)):
            prefixList[i + 1] = prefixList[i] + nums[i]
        
        # 遍历查找所有区间，前缀和为 k的，计数
        rst = 0
        for i in range(n):
            for j in range(i + 1, n + 1):
                if prefixList[j] - prefixList[i] == k:
                    rst += 1
        
        return rst


# 暴力优化解法，前缀和即可以累加获得，无需使用 列表表示
class Solution:
    def subarraySum(self, nums: list, k: int) -> int:
        """
            暴力破解优化
        """
        n, rst = len(nums), 0

        for i in range(n):
            prefixNum = 0
            for j in range(i, n):
                prefixNum += nums[j]
                if prefixNum == k:
                    rst += 1

        return rst

# 前缀和加上hash查找， 将线性的查找，变为hash查找，O(n) 变 O(1)
class Solution:
    def subarraySum(self, nums: list, k: int) -> int:
        """
            计算前缀和，hash查找
            前缀和暴力查找的关键点在于，找到所有的区间进行判断区间和是否等于 K： prefixList[j] - prefixList[i] == k
            那么可以将问题转换一下 prefixList[j] = prefixList[i] + k, 满足这样的条件，
            那么可以说明该 i --> j 的区间是满足条件的。那么我们就使用字典（键就是prefixList[i] + k，  因为可能多个 i 成立，这里要value是对应的计数）错误！！ [-1,-1,1]   0 这样的案例是不通过的

            再次变形一下，记录 prefixList[i] = prefixList[j] - k , 也是错误，跑不过上面的测试用例， 原因在于 要找之前的位置， 不能将prefixList[j] - k 生成好了全部再去找， prefixList[i]， 计算到当前位置就要往前找。
        """
        # 计算前缀和
        n = len(nums)
        prefixList = [0] * (n + 1)
        for i in range(len(nums)):
            prefixList[i + 1] = prefixList[i] + nums[i]
        

        # 记录 prefixList[j] - k
        rst = 0
        ikMap = dict()
        for j in range(len(prefixList)):
            # 先判断再加进去
            i = prefixList[j] - k
            if i in ikMap:
                rst += ikMap.get(i)
            ikMap[prefixList[j]] = ikMap.get(prefixList[j], 0) + 1

        return rst


# 最优解， 使用一个变量代替掉上面的前缀和列表
class Solution:
    def subarraySum(self, nums: list, k: int) -> int:
        """
            不需要计算前缀和了， 因为依次累加就是当前的前缀和，用一个变量替代前缀和数组
        """
        ikMap = dict()
        n, rst = len(nums), 0
        prefixNum = 0

        ikMap[0] = 1
        for j in range(n):
            prefixNum += nums[j]
            i = prefixNum - k
            rst += ikMap.get(i, 0)
            ikMap[prefixNum] = ikMap.get(prefixNum, 0) + 1

        return rst
